package com.canopys.study.open.test.algorithm.dynamic;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Author: Canopys
 * @Descrption:
 * @Date: Created in 20:27 2020/2/7
 * @Modified By:
 * 经典的数字三角形问题(简单易懂,经典动态规划);
 * 用二维数组存放数组三角形
 * D(r,j) 表示第r行第j个数字
 * MaxSum(r,j) 从D(r,j)到底边各条路径中，最佳路径的数字之和
 * 问题 求 MaxSum(1,1)
 *
 * 思路
 * 从D(r,j)出发，下一步只能是D(r+1,j)或者D(r+1,j+1).故对N行三角形
 * if (r == N) MaxSum(r,j)=D(r,j)
 * else MaxSum(r,j) = Max{MaxSum(r+1, j), MaxSum(r+1, j+1)} + D(r,j)
 */
public class Simple {
    public static List<List<Integer>> D = new ArrayList<>();
    public static Map<String, Integer> MAX = new HashMap<>();
    public static int MaxSum(int r, int j) {
        if (D.size() == r) {
            return D.get(r - 1).get(j - 1);
        } else {
            return Math.max(MaxSum(r+1, j), MaxSum(r+1, j+1)) + D.get(r-1).get(j-1);
        }
    }

    public static int MaxSumCac(int r, int j) {
        if (MAX.get(r + "#" + j) != null) {
            return MAX.get(r + "#" + j);
        }

        int max = -1;
        if (D.size() == r) {
            max = D.get(r - 1).get(j - 1);
        } else {
            max = Math.max(MaxSum(r+1, j), MaxSum(r+1, j+1)) + D.get(r-1).get(j-1);
        }
        MAX.put(r + "#" + j, max);
        return max;
    }

    public static void main(String[] args) {
        List<Integer> first = new ArrayList<>();
        first.add(1);
        List<Integer> sec = new ArrayList<>();
        sec.add(2);
        sec.add(3);
        List<Integer> third = new ArrayList<>();
        third.add(4);
        third.add(5);
        third.add(6);
        List<Integer> fourth = new ArrayList<>();
        fourth.add(7);
        fourth.add(8);
        fourth.add(9);
        fourth.add(10);

        List<Integer> fivth = new ArrayList<>();
        fivth.add(11);
        fivth.add(12);
        fivth.add(13);
        fivth.add(14);
        fivth.add(15);

        List<Integer> sixth = new ArrayList<>();
        sixth.add(11);
        sixth.add(12);
        sixth.add(13);
        sixth.add(14);
        sixth.add(15);
        sixth.add(17);
        sixth.add(19);

        List<Integer> seveth = new ArrayList<>();
        seveth.add(11);
        seveth.add(12);
        seveth.add(13);
        seveth.add(14);
        seveth.add(15);
        seveth.add(12);
        seveth.add(17);
        seveth.add(9);

        List<Integer> eigthth = new ArrayList<>();
        eigthth.add(11);
        eigthth.add(12);
        eigthth.add(13);
        eigthth.add(14);
        eigthth.add(15);
        eigthth.add(1);
        eigthth.add(3);
        eigthth.add(8);

        List<Integer> nith = new ArrayList<>();
        nith.add(11);
        nith.add(12);
        nith.add(13);
        nith.add(14);
        nith.add(15);
        nith.add(11);
        nith.add(12);
        nith.add(13);
        nith.add(14);

        D.add(first);
        D.add(sec);
        D.add(third);
        D.add(fourth);
        D.add(fivth);
        D.add(sixth);
        D.add(seveth);
        D.add(eigthth);
        D.add(nith);


        System.out.println(System.currentTimeMillis());
        int max = MaxSum(1, 1);
        System.out.println(max);
        System.out.println(System.currentTimeMillis());
        int maxCa = MaxSumCac(1, 1);
        System.out.println(maxCa);
        System.out.println(System.currentTimeMillis());

        System.out.println(longestPalindrome("a"));

        trap(new int[] {0,1,0,2,1,0,1,3,2,1,2,1});
    }

    public static String longestPalindrome(String s) {
        int length = s.length();
        int maxLen = 0;
        String maxStr = "";
        boolean [][] P = new boolean [length][length];
        for (int len = 1; len < length; len++) {
            for (int start = 0; start < length; start++) {
                int end = start + len -1;
                if (end >= length) {
                    break;
                }

                P[start][end] = (len == 1 || len == 2 || P[start+1][end-1]) && s.charAt(start) == s.charAt(end);
                if (P[start][end] && len > maxLen) {
                    maxStr = s.substring(start, end+1);
                }
            }
        }
        return maxStr;
    }

    public static int trap(int[] height) {
        int sum = 0;
        for (int i = 0; i < height.length; i++) {
            int max_r = 0;
            int max_l = 0;
            for (int j = 0; j <= i; j++) {
                max_r = Math.max(height[j], max_r);
            }
            for (int j = i; j < height.length; j++) {
                max_l = Math.max(height[j], max_l);
            }
            sum += Math.min(max_l, max_r) - height[i];
        }
        return sum;
    }
}
